package manacher

import (
	"math"
)

func GetMaxPalindromeSubsLen(s string) int {
	ans := math.MinInt64
	R := -1
	C := -1
	curI := 0
	ms := GetManacherStr(s)
	rArr := make([]int, len(ms))


	for curI < len(ms) {
		// 在R内 找到已经不用验证的位置是多大, 那个小取哪个
		if R > curI {
			rArr[curI] = Min(rArr[2*C - curI], R-curI)
		}
		// 开始向两边扩
		for curI+rArr[curI] < len(ms) && curI-rArr[curI] >= 0 &&
			ms[curI+rArr[curI]] == ms[curI-rArr[curI]] {
			rArr[curI]++
		}
		if curI + rArr[curI] > R {
			C = curI
			R = curI + rArr[curI]
		}
		ans = Max(ans, rArr[curI])
		curI++
	}
	return ans-1
}

func GetMaxPalindromeSubsStr(s string) string {
	ans := math.MinInt64
	R := -1
	C := -1
	curI := 0
	ms := GetManacherStr(s)
	rArr := make([]int, len(ms))
	maxI := -1
	maxR := -1

	for curI < len(ms) {
		// 在R内 找到已经不用验证的位置是多大, 那个小取哪个
		if R > curI {
			rArr[curI] = Min(rArr[2*C - curI], R-curI)
		}
		// 开始向两边扩
		for curI+rArr[curI] < len(ms) && curI-rArr[curI] >= 0 &&
			ms[curI+rArr[curI]] == ms[curI-rArr[curI]] {
			rArr[curI]++
		}
		if rArr[curI] > maxR {
			maxR = rArr[curI]
			maxI = curI
		}
		if curI + rArr[curI] > R {
			C = curI
			R = curI + rArr[curI]
		}
		ans = Max(ans, rArr[curI])
		curI++
	}
	return s[(maxI-maxR+1)/2:(maxI+maxR-1)/2]
}

func GetManacherStr(s string) string{
	ms := "#"
	for i:=0; i<len(s); i++ {
		ms += string(s[i])
		ms += "#"
	}
	return ms
}

func Min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func Max(a, b int) int {
	if a > b{
		return a
	}
	return b
}
